import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class Leetcode19 {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        int n = 3;

        ListNode res = new ListNode();
        createNode(res, list);
        ListNode target = removeNthFromEnd(res, n);
        System.out.println(target);
    }

    public static ListNode createNode(ListNode node, List<Integer> numbers) {
        if (numbers.isEmpty()) {
            return null;
        }

        node.val = numbers.get(0);
        ListNode next = new ListNode();
        numbers.remove(0);
        node.next = createNode(next, numbers);

        return node;
    }


    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next == null) {
            return null;
        }

        if (head.next.next == null) {
            if (n == 1) {
                head.next = null;
                return head;
            } else {
                return head.next;
            }
        }

        int count = 0;
        ListNode countNode = head;
        while (countNode != null) {
            count++;
            countNode = countNode.next;
        }
        int removeIndex = count - n;

        if (removeIndex == 0) {
            return head.next;
        }

        ListNode parent = head;
        ListNode current = head.next;
        ListNode next = head.next.next;
        int loopIndex = 0;
        while (current != null) {
            if (removeIndex == loopIndex + 1) {
                parent.next = next;
            }

            parent = current;
            current = next;
            if (next != null) {
                next = next.next;
            }

            loopIndex++;
        }

        return head;
    }

    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

}

 class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public static ListNode createNode(ListNode node, List<Integer> numbers) {
        if (numbers.isEmpty()) {
            return null;
        }

        node.val = numbers.get(0);
        ListNode next = new ListNode();
        numbers.remove(0);
        node.next = createNode(next, numbers);

        return node;
    }
}
